﻿// 0915train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <deque>

using namespace std;

/*
 项目组共有N个开发人员，项目经理接到了M个独立的需求，
 每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作
 假定各个需求之间无任何先后依赖关系，请设计算法帮助项目经理进行工作安排，
 使整个项目能用最少的时间交付。

输入描述
第一行输入为M个需求的工作量，单位为天，用逗号隔开。
例如：X1 X2 X3 … Xm 。表示共有M个需求，每个需求的工作量分别为X1天，X2天…Xm天。
其中0 < M < 30；0 < Xm < 200
第二行输入为项目组人员数量N

输出描述
最快完成所有工作的天数

输入
6 2 7 7 9 3 2 1 3 11 4
2
输出
28

 */
class Solution01
{
public:
    bool checkVerify(vector<int>& weight_vec, int box_total_w)
    {
        vector<int>box_vec(total_count_, box_total_w);

        int w_size = weight_vec.size();
        for (int i=0; i<w_size; i++)
        {
            int curr_w = weight_vec[i];
            bool is_find = false;
            for (auto&box_w:box_vec)
            {
                if (box_w>=curr_w)
                {
                    box_w -= curr_w;
                    is_find = true;
                    break;
                }
	            
            }
            if (!is_find)
            {
                return false;
            }
        }
        return true;
        //checkVerify
    }
    Solution01(vector<int>&weight_vec, int N)
    {
        total_count_ = N;
        sort(weight_vec.rbegin(), weight_vec.rend());

        int sum = 0;
        for (auto&num: weight_vec)
        {
            sum += num;
        }
        int left = weight_vec[0], right = sum + 1;

        int result = INT_MAX;
        while (left<right)
        {
            int mid = left + (right - left) / 2;

            if (checkVerify(weight_vec,mid))
            {
                //当前容量合格，可以装下全部工作
                //缩小容量
                result = mid;
                right = mid;
            }
            else
            {
                left = mid + 1;
            }

            //while
        }
        cout << result;
        //Solution01
    }
private:
    int total_count_ = 0;
};


/*
有一个总空间为100字节的堆，现要从中新申请一块内存
内存分配原则为优先紧接着前一块已使用内存分配空间
且最接近申请大小的空闲内存

输入描述
第1行是1个整数，表示期望申请的内存字节
第2到N行是用空格分割的两个整数，表示当前已分配的内存的情况，
每一行表示一块已分配的连续内存空间，每行的第1和第2个整数分别表示偏移地址和内存块大小，
如:0 1 3 2分别表示0偏移地址开始的1个字节和3偏移地址开始的2个字节已被分配，
其余内存空闲

输出描述
若申请成功，输出申请到内存的偏移；若申请失败，输出-1

输入
1
0 1
3 2
输出
1

堆中已使用的两块内存是偏移从0开始1字节和偏移从3开始的2字节，
空闲的两块内存是偏移从1开始2个字节和偏移从5开始的95个字节，
根据分配原则，新申请的内存应从1开始分配1个字节，所以输出移为1
 */
class Solution02
{
public:
    vector<vector<int>>getInterval(vector<vector<int>>&origin_vec)
    {
        vector<vector<int>>interval_vec;

        for (auto&item:origin_vec)
        {
            vector<int>interval_item(2);
            interval_item[0] = item[0];
            interval_item[1] = item[0] + item[1];
            interval_vec.push_back(interval_item);
        }
        return interval_vec;
    }

    Solution02(vector<vector<int>>&origin_vec, int target_buffer_size)
    {
        vector<vector<int>>interval_vec = getInterval(origin_vec);

        int v_size = interval_vec.size();

        sort(interval_vec.begin(), interval_vec.end(), [](vector<int>&vec_1, vector<int>&vec_2)
            {
                return vec_1[0] < vec_2[0];
            });

        //先判断是否有重叠
        bool is_verify = true;
        for (int i=1; i<v_size; i++)
        {
            int last_end = interval_vec[i - 1][1];
            int curr_start = interval_vec[i][0];

            //越界
            if (last_end>curr_start)
            {
                is_verify = false;
            }
        }

        if (!is_verify)
        {
            cout << -1;
            return;
        }

        //计算间隔
        vector<vector<int>>new_interval = { {-1,0} };
        for (auto&vec_i:interval_vec)
        {
            new_interval.push_back(vec_i);
        }
        new_interval.push_back({ 100,101 });

        interval_vec = new_interval;
        v_size = interval_vec.size();

        int res = -1;
        int min_buffer_size = 100;
        //塞进{-1,0}用于维护0-interval_vec[0][0]这段区域
        //塞进{100,101}用于维护interval_vec[v_size-1][1]-100这段区域
        for (int i=1; i<v_size; i++)
        {
            int last_end = interval_vec[i - 1][1];
            int curr_start = interval_vec[i][0];

            //紧挨着已使用，最接近待分配内存的大小
            int curr_available = curr_start - last_end;
            if (min_buffer_size > curr_available&& curr_available>=target_buffer_size)
            {
                res = last_end;
                min_buffer_size = curr_available;
            }
        }
        cout << res;
        //Solution02
    }
};


/*
 用数组代表每个人的能力，一个比赛活动要求参赛团队的最低能力值为N，
 每个团队可以由1人或2人组成，且1个人只能参加1个团队，
 请计算出最多可以派出多少支符合要求的团队？
 输入描述
 第一行数组代表总人数
 第二行数组代表每个人的能力
 第三行数值为团队要求的最低能力值

输出描述
最多可以派出的团队数量

输入
5
3 1 5 7 9
8
输出
3
3和5组成一队，1和7组成一队，9自己一个队，故输出3
 */
class Solution03
{
public:
    Solution03(vector<int>&num_vec, int lower)
    {
        sort(num_vec.rbegin(), num_vec.rend());

        int result = 0;
        vector<int>remain_vec;
        for (int i=0; i<num_vec.size();i++)
        {
	        if (num_vec[i]<lower)
	        {
                remain_vec.push_back(num_vec[i]);
	        }
            else
            {
                result += 1;
            }
        }

        int left = 0, right = remain_vec.size()-1;

        while (left<right)
        {
            if (remain_vec[left]+remain_vec[right]>=lower)
            {
                result += 1;
                left++;
                right--;
            }
            else
            {
                //数组是倒序的，后面的数字小
                right--;
            }
        }

        cout << result;
	    //Solution03
    }
};


/*
 给定一个由若干整数组成的数组nums ，可以在数组内的任意位置进行分割，
 将该数组分割成两个非空子数组（即左数组和右数组），分别对子数组求和得到两个值，
 计算这两个值的差值，请输出所有分割方案中，差值最大的值。

输入描述
第一行输入数组中元素个数n，1 < n <= 100000
第二行输入数字序列，以空格进行分隔，数字取值为4字节整数

输出描述
输出差值的最大取值

输入
6
1 -2 3 4 -9 7
输出
10
 */
class Solution04
{
public:
    Solution04(vector<int>&num_vec)
    {
        int v_size = num_vec.size();

        vector<int>pre_sum(v_size + 1);
        for (int i=1; i<=v_size; i++)
        {
            pre_sum[i] = pre_sum[i - 1] + num_vec[i - 1];
        }

        int max_diff = 0;
        for (int i=1; i<=v_size-1; i++)
        {
            int total_sum = pre_sum[v_size];

            int left_sum = pre_sum[i];
            int right_sum = total_sum - pre_sum[i];

            int curr_diff = abs(right_sum - left_sum);
            max_diff = max(curr_diff, max_diff);
        }
        cout << max_diff;
        //Solution04
    }
};

int main()
{
	//{
 //       int v_size;
 //       cin >> v_size;
 //       vector<int>num_vec(v_size);
 //       for (int i = 0; i < v_size; i++)
 //       {
 //           cin >> num_vec[i];
 //       }

 //       Solution04 solu(num_vec);

 //       return 0;
	//}
	//{
 //       int v_size;
 //       cin >> v_size;

 //       vector<int>num_vec(v_size);
 //       for (int i=0; i<v_size; i++)
 //       {
 //           cin >> num_vec[i];
 //       }

 //       int lower;
 //       cin >> lower;

 //       Solution03 solu(num_vec, lower);

 //       return 0;
	//}
	{
        int target_buffer_size;
        cin >> target_buffer_size;
        cin.ignore();

        vector<vector<int>>origin_vec;

        string input;
        while (getline(cin,input))
        {
            if (input.empty())break;
            stringstream oh_sstream(input);
            string token;
            vector<int>item_vec;
            while (oh_sstream>>token)
            {
                item_vec.push_back(stoi(token));
            }
            origin_vec.push_back(item_vec);
        }

        Solution02 solu(origin_vec, target_buffer_size);

        return 0;
	}
    string input;
    getline(cin, input);

    stringstream oh_sstream(input);
    string token;

    vector<int>weight_vec;
    while (oh_sstream>>token)
    {
        weight_vec.push_back(stoi(token));
    }

    int N;
    cin >> N;

    Solution01 solu(weight_vec, N);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
